package star.动态规划.青蛙跳台阶;

public class NumWays {
    public int numWays(int n){
        if (n==0 || n==1) return 1;
        if (n==2) return 2;
        int a = 1;
        int b = 2;
        int c = a + b;
        for (int i = 2; i < n; i++) {
            a = b;
            b = c;
            c = a + b;
        }
        return c;
    }
    public int numWays2(int n){
        if (n==0 || n==1) return 1;
        if (n==2) return 2;
        int[] arr = new int[n];
        arr[0] = 1;
        arr[1] = 2;
        for (int i = 2; i < n; i++) {
            arr[i] = arr[i-1] + arr[i-2];
        }
        return arr[n-1];
    }
}
